#include <stdio.h>
#include <stdlib.h>

/**
 * 最小质因子筛（MPF Sieve）：求小于等于n的所有素数
 * @param n: 上限值
 * @param prime_count: 输出参数，返回素数的个数
 * @return: 存储素数的动态数组（需调用者手动释放），失败返回NULL
 */
int* sieve(int n, int* prime_count) {
    // 特殊情况处理：n<2时无素数
    if (n < 2) {
        *prime_count = 0;
        return NULL;
    }

    // 1. 初始化最小质因子数组（mpfs），对应Python的 [0]*(n+1)
    int* mpfs = (int*)calloc(n + 1, sizeof(int));
    if (!mpfs) {
        fprintf(stderr, "内存分配失败！\n");
        *prime_count = 0;
        return NULL;
    }

    // 2. 动态数组存储素数（pn），初始分配4个空间，后续按需扩容
    int pn_cap = 4;
    int* pn = (int*)malloc(pn_cap * sizeof(int));
    if (!pn) {
        fprintf(stderr, "内存分配失败！\n");
        free(mpfs);
        *prime_count = 0;
        return NULL;
    }
    int pn_len = 0; // 素数数组当前长度

    // 3. 核心筛选逻辑（完全复刻Python）
    for (int i = 2; i <= n; i++) {
        int mpf = mpfs[i];
        if (mpf == 0) {
            // i是素数，加入pn数组
            if (pn_len >= pn_cap) {
                // 扩容：容量翻倍
                pn_cap *= 2;
                int* temp = (int*)realloc(pn, pn_cap * sizeof(int));
                if (!temp) {
                    fprintf(stderr, "内存分配失败！\n");
                    free(mpfs);
                    free(pn);
                    *prime_count = 0;
                    return NULL;
                }
                pn = temp;
            }
            pn[pn_len++] = i;
            mpf = i;
        }

        // 遍历已找到的素数p
        for (int p_idx = 0; p_idx < pn_len; p_idx++) {
            int p = pn[p_idx];
            if (p > mpf) {
                break; // p > 当前最小质因子，退出循环
            }
            int x = p * i;
            if (x > n) {
                break; // 超出上限，退出循环
            }
            mpfs[x] = p; // 设置x的最小质因子为p
        }
    }

    // 4. 释放最小质因子数组，调整素数数组大小（可选，优化内存）
    free(mpfs);
    int* primes = (int*)realloc(pn, pn_len * sizeof(int));
    if (!primes) {
        primes = pn; // 扩容失败时，使用原数组
    }

    // 设置输出参数
    *prime_count = pn_len;
    return primes;
}

// 测试主函数
int main() {
    int n = 20;
    int prime_count = 0;
    int* primes = sieve(n, &prime_count);

    if (primes) {
        printf("小于等于%d的素数：[", n);
        for (int i = 0; i < prime_count; i++) {
            printf("%d", primes[i]);
            if (i != prime_count - 1) {
                printf(", ");
            }
        }
        printf("]\n");

        // 释放动态数组内存
        free(primes);
    } else {
        if (n < 2) {
            printf("小于%d的素数不存在！\n", n);
        } else {
            printf("素数计算失败！\n");
        }
    }

    return 0;
}